/*
	树的双亲表示法(顺序存储结构)
	用一组连续的存储空间来存储树的结点,同时
	在每个结点附加一个指示器(整数域),用以指示双亲结点的位置

*/
#define MAX_SIZE 100
typedef int ElemType;


/*

typedef struct ptnNode
{
	ElemType data;
	int parent;
}PTNode;

/*
	利用任一结点的父节点唯一的性质.
	可以方便的直接找到任意结点的父节点,
	求结点的子结点时需要遍历整个数组
*/

/*
typedef struct 
{
	PTNode Node[MAX_SIZE];
	int root;/*根结点的位置*/
//	int num;/*结点数*/
//};


/*
	孩子链表表示法
	树中每个结点有多个指针域,每个指针指向其一颗子树的根结点.
	有两种结点结构
	1.定长结点结构
	指针域的数目就是树的度
	其特点时:链表结点简单,但指针域的浪费
	在一棵有n各结点,度为k的树中必有n(k-1)+1空指针

	2.不定长结点结构
	树中每个结点的指针域数目不同,是该结点的度.
	没有多余的指针域,操作不便
*/

/*
typedef struct listnode
{
	int childno;/*孩子结点编号*/
//	struct list *next;
//}CTNode; /*表结点结构*/

/*
typedef struct 
{
	ElemType data;
	CTNode *firstchild;
}HNode;/*头结点结构*/



/*
	孩子兄弟表示法(二叉树表示法):
*/

typedef struct CSNode
{
	ElemType data;
	struct CSNode *firstchild, *nextsibling
}CSNode;


//计算树的叶子结点,递归算法,只要左树是空就加一
int countLeave(CSNode *T)
{
	if (T -> firstchild == NULL && T -> nextsibling == NULL)
		return 1;
	if (T -> firstchild == NULL)
		return 1 + countLeave(T -> nextsibling);
	if (T -> firstchild != NULL)
		return countLeave(T -> nextsibling);
}

/*
	递归算法计算树的深度
	递归思想:
	1.如果树是空则高度是1
	2.如果不是空的,高度是 1+{其左子树和右子树比较后的大者}

*/

int depth(CSNode *T)
{
	int hc,hs;//hc表示左子树的高度,hs表示右子树的高度

	if (T -> firstchild == NULL && T -> nextsibling == NULL)
		return 0;
	else
	{
		hc = 1 + depth(T -> firstchild);
		hs = 1 + depth(T -> nextsibling);

		if (hc > hs)
			return hc;
		else
			return hs;
	}
}


/*
	构造孩子兄弟树
	输入:树的层次序列,以及每个结点的度
*/
void creatCSTree(CSNode *T, ElemType e[], int degree[], int n)
{
	CSNode *list[MAX_SIZE],*p;

	int i,j,k = 0,d;

	for (i = 0; i < n; i++)
	{
		p = (CSNode *)malloc(sizeof(CSNode));
		p -> data = e[i];
		p -> firstchild = p -> nextsibling = NULL;
		list[i]  = p;
		//list[i] -> firstchild = list[i] -> nextsibling = NULL;
	}

	for (i = 0; i < n; i++)
	{
		d = degree[i];

		if (d)
		{
			k++;

			list[i] -> firstchild = list[k];

			for (j = 1 ; j < d; j++)
			{
				list[i+j] -> nextsibling = list[i+j+1];
				k++;
			}
		}
	}
}
